//给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
// 
//
// 注意：字符串长度 和 k 不会超过 104。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "ABAB", k = 2
//输出：4
//解释：用两个'A'替换为两个'B',反之亦然。
// 
//
// 示例 2： 
//
// 
//输入：s = "AABABBA", k = 1
//输出：4
//解释：
//将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
//子串 "BBBB" 有最长重复字母, 答案为 4。
// 
// Related Topics 哈希表 字符串 滑动窗口 
// 👍 458 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class LongestRepeatingCharacterReplacement {
    public static void main(String[] args) {
        Solution solution = new LongestRepeatingCharacterReplacement().new Solution();
        System.out.println(solution.characterReplacement("AABABBA",1));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 将问题转化为找最长区间问题，筛选条件为，区间内非众数个数小于k
        // 套滑动窗口模板
        public int characterReplacement(String s, int k) {
            int slow = 0;
            int fast = 0;
            int n = s.length();
            // 用定长数组代替哈希表
            int[] map = new int[26];
            int res = 0;
            int maxCount = 0;
            while (fast < n) {
                char cur = s.charAt(fast);
                map[cur-'A']+=1;
                maxCount = Math.max(maxCount,map[cur-'A']);
                while (fast - slow + 1 - maxCount > k) {
                    cur = s.charAt(slow);
                    map[cur-'A']-=1;
                    slow++;
                }
                res = Math.max(res,fast-slow+1);//用大于号比较，性能更高
                fast++;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}